package com.hard;

import com.sun.istack.internal.NotNull;

import javax.tools.JavaCompiler;
import javax.tools.ToolProvider;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by Lxk on 2019/7/27.
 */
public class Solution480 {
    /**
     * 需要取滑动窗口中位数，
     * 滑动窗口需要考虑两点：1、保证值有序；2、确保窗口中数字数目不超出
     * 拿中位数时需要考虑窗口中数字个数的奇数偶数
     * @param nums
     * @param k
     * @return
     */
    public double[] medianSlidingWindow(@NotNull int[] nums, int k) {
        List<Integer> window = new LinkedList<>();
        double[] res = new double[nums.length-k+1];
        int resPos = 0;
        for(int i = 0;i < nums.length ;i++){
            int pos = window.size()>0 ? window.size() : -1;
            while(pos>=1&&nums[window.get(pos-1)]<nums[i]){
                pos--;
            }
            //新元素放入窗口
            if(pos>=0){
                window.add(pos,i);
            }
            if(window.size()==0){
                window.add(i);
            }
            //旧元素移出窗口
            if(window.size()>k){
                for(int t = 0;t <window.size(); t++){
                    if(window.get(t)<i-k+1){
                        window.remove(t);
                        break;
                    }
                }
            }
            if(window.size()==k){
                if(window.size()%2==0){
                    res[resPos++] = ((double)nums[window.get(window.size()/2)] + (double) nums[window.get((window.size()/2)-1)])/2;
                }else{
                    res[resPos++] = nums[window.get(window.size()/2)];
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1,5,2,6};
        Solution480 solution480 = new Solution480();
        double[] res = solution480.medianSlidingWindow(null,4);
        System.out.println(res);
    }

}
